/**
 * describe:
 *
 * @author chaP
 * @date 2018/12/26
 */
package CodingTest;
/**
 *题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 示例:

 输入: [-2,1,-3,4,-1,2,1,-5,4],
 输出: 6
 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

 /////////////////////////////////////////////////////////////////////////////////////////////////////
                                            动态规划法：
 **************************************************************************************************
 首先，我们把原问题转化为一个等价的描述：

 给定一个整数数组nums，长度为N。

 设Fk为：以数列中第k项结尾的全部连续子数组中具有最大和的那一个子数组的和；

 求F1,...,FN中的最大值。

 **************************************************************************************************

具体地阐述一下Fk的含义，比如k=3时，nums[3]==-1，以4结尾的全部连续子数组包括：

        -1； 和为-1

        2 -1； 和为1

        -3  2 -1； 和为-2

        2 -3  2 -1； 和为0

        具有最大和的数组为上述的第二个数组，那么F3等于1.

**************************************************************************************************

        我们具体地看上面定义的这个新问题，按上述思路，数组2 -3  2 -1  3的F0→F4分别为：

        F0:     2                                        F0= 2    是所有以2结尾的子数组中的具有最大和的那个子数组的和

        F1:     2  -3                                   F1=-1   是所有以-3结尾的子数组中的具有最大和的那个子数组的和

        F2:     _   _   2                              F2= 2    是所有以2结尾的子数组中的具有最大和的那个子数组的和

        F3:     _   _   2   -1                        F3= 1   是所有以-1结尾的子数组中的具有最大和的那个子数组的和

        F4:     _   _   2   -1   3                   F4= 4   是所有以3结尾的子数组中的具有最大和的那个子数组的和 

        可以看到，F(k+1)要么等于F(k)加上nums[k+1]（说明此时nums[k+1]是个正数），要么等于nums[k+1]本身。

        显然，这个新问题是与原问题等价的。因为在本质上我们已经遍历了所有可能的情况。

        而对于Fk来讲，F1,...,Fk-1都是Fk的子问题：因为从k→1，问题的形式是相同的，但规模不断缩小。当k==1时，这就变成了一个平凡的问题。

        用更专业的话术来讲，新问题Fk称为“状态”，从状态到状态之间，存在着状态转移方程：

        F[i+1] = max(F[i]+nums[i+1]，nums[i+1])，

        化简之后，就是比较F[i] ?> 0 (F[i] + nums[i+1] ?> nums[i+1])。
        ---------------------
 /////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                                                    分治法：
 略复杂
 */



public class maxSubArray {
    public int maxSubArray(int[] nums){
        int res = nums[0];
        int sum = 0;
        for(int num:nums){
            if(sum >0)
                sum += num;
            else
                sum = num;
            res = Math.max(res,sum);
        }
        return res;
    }
}
